package btree;

/**
 * BTree树的节点
 * @Auther: wangbw
 * @Date:2020/8/14
 * @Description: btree
 * @version: 1.0
 */
public class BTNode<K extends Comparable<K>, V> {
	//根节点
	private BTNode<K,V> root;
	//是否是叶子节点
	protected boolean isLeaf;
	//当前节点中键的数量
	protected int currentKeyNum;
	//当前节点中键值对数组
	protected BTKeyValue<K, V>[] keys;
	//用于存子节点的数组
	protected BTNode<K, V>[] children;

	public BTNode() {
		isLeaf = true;
		currentKeyNum = 0;
		keys = new BTKeyValue[Constants.UPPER_BOUND_KEYNUM];
		children = new BTNode[Constants.UPPER_BOUND_KEYNUM];
	}

	/**
	 * 获取指定位置的孩子节点
	 * @param btNode   当前节点
	 * @param keyIndex  当前键的索引位置
	 * @param offset    偏移量
	 * @return
	 */
	protected static BTNode<?, ?> getChildAtIndex(BTNode<?,?> btNode, int keyIndex, int offset){
		if(btNode.isLeaf)
			return null;
		int targetIndex = keyIndex + offset;
		if(targetIndex < 0 || targetIndex > btNode.currentKeyNum)
			throw new IllegalArgumentException("数组越界， 目标值"+ targetIndex + "实际值：" + btNode.currentKeyNum);
		return btNode.children[targetIndex];
	}

	/**
	 * 返回btNode节点中位于keyIdx位上的键左边的子节点(紧挨着)。
	 * 偏移量为0， 因为孩子节点比键多一个，键的范围是从0到currentKeyNum，孩子的范围是从0到currentKeyNum + 1.
	 * 所以偏移量为0，表示就是向左倾斜的一条线。
	 * @param btNode
	 * @param keyIdx
	 * @return
	 */
	protected static BTNode<?,?> getLeftChildAtIndex(BTNode<?,?> btNode, int keyIdx){
		return getChildAtIndex(btNode, keyIdx,0);
	}

	/**
	 * 返回btNode节点中位于keyIdx位上的键右边的子节点(紧挨着)。
	 * @param btNode
	 * @param keyIdx
	 * @return
	 */
	protected static BTNode<?,?> getRightChildAtIndex(BTNode<?,?> btNode, int keyIdx){
		return getChildAtIndex(btNode, keyIdx,1);
	}

	/**
	 * 返回父节点的keyIndx上的子节点的左兄弟节点
	 * 偏移量-1， 是为了抛出自己。
	 * @param parentNode
	 * @param keyIdx
	 * @return
	 */
	protected static BTNode<?,?> getLeftSiblingAtIndex(BTNode<?,?> parentNode, int keyIdx){
		return getChildAtIndex(parentNode, keyIdx, -1);
	}

	/**
	 * 返回父节点的keyIndx上的子节点的右兄弟节点
	 * @param parentNode
	 * @param keyIdx
	 * @return
	 */
	protected static BTNode<?,?> getRightSiblingAtIndex(BTNode<?,?> parentNode, int keyIdx){
		return getChildAtIndex(parentNode, keyIdx, 1);
	}

	/**
	 * 判断父节点的keyIndex 上的子节点是否存在左兄弟节点
	 * @param parentNode
	 * @param keyIdx
	 * @return
	 */
	protected static boolean hasLeftSiblingAtIndex(BTNode<?,?> parentNode, int keyIdx){
		if(keyIdx - 1 < 0 )
			return false;
		else
			return true;
	}

	/**
	 * 判断父节点的keyIndex 上的子节点是否存在左兄弟节点
	 * @param parentNode
	 * @param keyIdx
	 * @return
	 */
	protected static boolean hasRightSiblingAtIndex(BTNode<?,?> parentNode, int keyIdx){
		if(keyIdx - 1 < 0 )
			return false;
		else
			return true;
	}

	/**
	 * 将该节点x分裂为含有一个键值对的父节点和两个子节点， 并返回父节点的连接。
	 * @param x
	 * @return
	 */
	private BTNode<K, V> split(BTNode<K, V> x){
		BTNode<K, V> leftNode, rightNode, midNode;
		leftNode = new BTNode<K, V>();
		rightNode = new BTNode<K, V>();
		midNode = new BTNode<K, V>();

		int mid = x.currentKeyNum / 2;

		//左子树逻辑
		for (int i = 0; i < mid; i++) {
			leftNode.children[i] = x.children[i];
			leftNode.keys[i] = x.keys[i];
		}
		leftNode.children[mid] = x.children[mid];
		leftNode.isLeaf = x.isLeaf;
		leftNode.currentKeyNum = mid;

		//右子树逻辑
		for (int i = mid + 1; i < x.currentKeyNum; i++) {
			rightNode.children[i - mid - 1] = x.children[i];
			rightNode.keys[i - mid - 1] = x.keys[i];
		}
		rightNode.children[x.currentKeyNum - mid - 1] = x.children[x.currentKeyNum];
		rightNode.isLeaf = x.isLeaf;
		rightNode.currentKeyNum = x.currentKeyNum - mid - 1;

		midNode.keys[0] = x.keys[mid];
		midNode.currentKeyNum = 1;
		midNode.isLeaf = false;
		midNode.children[0] = leftNode;
		midNode.children[1] = rightNode;
		return midNode;
    }

	/**
	 * 从右节点借一个键值对过来
	 * @param x 父节点
	 * @param possibleIdx 需要补充键值对的    子节点的索引
	 * @return
	 */
	private BTNode<K, V> rightRotate(BTNode<K, V> x, int possibleIdx){
		//获取x的右子节点
		BTNode<K, V> rightNode = x.children[possibleIdx + 1];
		BTKeyValue<K, V> rightKey = rightNode.keys[0];
		BTNode<K, V> rightFirstNode = rightNode.children[0];
		//获取父节点交换位置的键值对
		BTKeyValue<K, V> topKey = x.keys[possibleIdx];
		//获取x的左子节点
		BTNode<K, V> leftNode = x.children[possibleIdx];
		leftNode.keys[leftNode.currentKeyNum] = topKey;
		leftNode.children[leftNode.currentKeyNum+1] = rightFirstNode;
		leftNode.currentKeyNum++;
		x.keys[possibleIdx] = rightKey;
		//将右边的节点和孩子节点整体往前移动一位
		for (int i = 0; i < rightNode.currentKeyNum - 1; i++) {
			rightNode.keys[i] = rightNode.keys[i+1];
			rightNode.children[i] = rightNode.children[i+1];
		}
		rightNode.children[rightNode.currentKeyNum-1] = rightNode.children[rightNode.currentKeyNum];
		rightNode.keys[rightNode.currentKeyNum - 1] = null;
		rightNode.children[rightNode.currentKeyNum] = null;
		rightNode.currentKeyNum--;
        return x;
    }

	/**
	 * 从左节点借一个键值对过来
	 * @param x 父节点
	 * @param possibleIdx 需要补充键值对的    子节点的索引
	 * @return
	 */
	private BTNode<K, V> leftRotate(BTNode<K, V> x, int possibleIdx){
		//获取x的左子节点
		BTNode<K, V> leftNode = x.children[possibleIdx - 1];
		BTKeyValue<K, V> leftKey = leftNode.keys[leftNode.currentKeyNum-1];
		BTNode<K, V> leftLastNode = leftNode.children[leftNode.currentKeyNum];
		//获取父节点交换位置的键值对
		BTKeyValue<K, V> topKey = x.keys[possibleIdx];
		//获取需要补齐键值对的节点， 并移动其中的键值对， 将最低位空出来， 用来填充从父节点交换过来的键值对
		BTNode<K, V> rightNode = x.children[possibleIdx];
		for (int i = rightNode.currentKeyNum; i > 0; i--) {
			rightNode.keys[i] = rightNode.keys[i - 1];
		}
		for (int i = rightNode.currentKeyNum + 1; i > 0; i--) {
			rightNode.children[i] = rightNode.children[i - 1];
		}

		rightNode.keys[0] = topKey;
		rightNode.children[0] = leftLastNode;
		rightNode.currentKeyNum++;
		x.keys[possibleIdx - 1] = leftKey;
		leftNode.keys[leftNode.currentKeyNum-1] = null;
		leftNode.children[leftNode.currentKeyNum] = null;
		leftNode.currentKeyNum--;
		return x;
	}

	/**
	 * 合并父节点位于possibleIdx 和 possibleIndx + 1 处的两节点。
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private  BTNode<K, V> rightMerge(BTNode<K, V> x, int possibleIdx){
		return leftMerge(x, possibleIdx +1);
	}

	/**
	 * 向左合并
	 * @param x
	 * @param possibleIdx   父节点中右孩子的索引。
	 * @return
	 */
	private BTNode<K,V> leftMerge(BTNode<K,V> x, int possibleIdx) {
		//获取左节点，
		BTNode<K, V> leftNode = x.children[possibleIdx - 1];
		//获取待合并到左节点的父节点
		BTKeyValue<K, V> topKey = x.keys[possibleIdx - 1];
		//获取右节点
		BTNode<K, V> possibleNode = x.children[possibleIdx];
		//先放父节点获取的键值对放入左节点，然后将右节点加入左节点
		leftNode.keys[leftNode.currentKeyNum] = topKey;
		for (int i = 0; i < possibleNode.currentKeyNum; i++) {
			leftNode.keys[leftNode.currentKeyNum + 1 + i] = possibleNode.keys[i];
		}
		for (int i = 0; i < possibleNode.currentKeyNum + 1; i++) {
			leftNode.children[leftNode.currentKeyNum + 1 + i] = possibleNode.children[i];
		}
		leftNode.currentKeyNum += possibleNode.currentKeyNum + 1;
		//更新父节点
		for (int i = possibleIdx - 1; i < x.currentKeyNum - 1; i++) {
			x.keys[i] = x.keys[i + 1];
		}
		x.keys[x.currentKeyNum - 1] = null;
		for (int i = possibleIdx; i < x.currentKeyNum; i++) {
			x.children[i] = x.children[i + 1];
		}
		x.children[x.currentKeyNum] = null;
		x.currentKeyNum--;
		return x;
	}

	public BTKeyValue minKey(){
		return minKey(root);
	}

	/**
	 * 获取指定节点子树中最小的节点
	 * @param node
	 * @return
	 */
	private BTKeyValue minKey(BTNode<K,V> node) {
		if (node== null)
			return null;
		if(node.children[0] != null){
			return minKey(node.children[0]);
		}else {
			return node.keys[0];
		}
	}

	public BTKeyValue maxKey(){
		return minKey(root);
	}

	/**
	 * 获取指定节点子树中最小的节点
	 * @param node
	 * @return
	 */
	private BTKeyValue maxKey(BTNode<K,V> node) {
		if (node== null)
			return null;
		if(node.children[node.currentKeyNum] != null){
			return maxKey(node.children[node.currentKeyNum]);
		}else {
			return node.keys[node.currentKeyNum];
		}
	}
}
